#include <bits/stdc++.h>
#include <cstdlib>
#include <queue>
#include <vector>
using namespace std;

struct Node {

  int machine;
  int vcpu;
  int mem;
  // 每个物理主机使用的CPU
  // 每个物理主机使用的内存的容量
  //    bool operator<(const Node &x, const Node &y)
  //    {
  //        return x.vcpu > y.vcpu || x.vcup == y.vcpu && x.mem > y.mem;
  //    }
  //
  //	bool operator <(   const  Node &y) {
  //		return   vcup<y.vcup ||    vcup==y.vcup &&    mem<y.mem;
  //	}
};

bool cmp2(Node x, Node y) {
  return x.vcpu > y.vcpu || x.vcpu == y.vcpu && x.mem > y.mem;
}

bool cmp(Node x, Node y) { return x.machine < y.machine; }

struct Scheduler {
  int total_vcpu;
  int total_mem;

  vector<int> id_to_pos;
  vector<int> cup_to_pos;
  vector<int> mem_to_pos;

  vector<Node> Q;

  Scheduler() {}

  void init(int n, int c, int m) {
    cout << "init..";
    // 每个物理机上地 cup和内存
    total_vcpu = c, total_mem = m;
    //		used_vcpu.resize(n,0);
    //		used_mem.resize(n,0);

    for (int i = 0; i < n; i++) {
      Q.push_back(Node{i, 0, 0});
    }
  }

  // #需要选手返回给系统在编号为<machine_id>的机器上创建该虚拟机。
  // # 如果需要扩容， 那么选手还需返回扩容台数（不扩容返回0） ，
  // #  这些新增物理主机的编号在当前物理主机的编号上依次递增
  pair<int, int> create(int id, int vcpu, int mem) {

    sort(Q.begin(), Q.end(), cmp2);
    bool flag = false;
    int pos = Q.size();
    for (int i = 0; i < Q.size(); i++) {
      if ((Q[i].vcpu + vcpu <= total_vcpu && Q[i].mem + mem <= total_mem)) {
        pos = Q[i].machine;
        // 每个虚拟主机的信息
        id_to_pos.push_back(pos);
        cup_to_pos.push_back(vcpu);
        mem_to_pos.push_back(mem);

        // genxin 每个物理主机的信息
        Q[i].vcpu += vcpu;
        Q[i].mem += mem;
        flag = true;
        break;
      }
    }
    if (flag) {
      return make_pair(pos, 0);
    } else {

      Q.push_back(Node{pos, 0, 0});
      // 添加每个虚拟主机的信息
      id_to_pos.push_back(pos);
      cup_to_pos.push_back(vcpu);
      mem_to_pos.push_back(mem);

      return make_pair(pos, 1);
    }
  }

  // #表示删除编号<id>的虚拟机，
  // # pos是物理主机  id是虚拟主机的id号
  void remove(int id) {
    cout << "remove";
    int pos = id_to_pos[id];
    for (int i = 0; i < Q.size(); i++) {
      if (Q[i].machine == pos) {
        Q[i].vcpu -= cup_to_pos[id];
        Q[i].mem -= mem_to_pos[id];
      }
    }
  }
};